package daily_exercise;

import java.util.*;

public class Demo3 {



    // 1491. 去掉最低工资和最高工资后的工资平均值
    public static double average(int[] salary) {
        int sum = 0, max = Integer.MIN_VALUE, min = Integer.MAX_VALUE;
        for (int x : salary) {
            sum += x;
            if (x > max) max = x;
            if (x < min) min = x;
        }

        double res = 1.0 * (sum - max - min) / (salary.length - 2);
        return res;
    }



    // 2079. 给植物浇水
    public int wateringPlants(int[] plants, int capacity) {
        // [2,2,3,3]     5
        int n = plants.length;
        int step = 0, rest = capacity;
        for (int i = 0; i < n; ) {
            if (rest >= plants[i]) {
                step++;
                rest -= plants[i++];
            } else {
                step += 2 * i + 1;
                rest = capacity - plants[i++];
            }
        }
        return step;
    }



    // 2105. 给植物浇水 II
    public int minimumRefill(int[] plants, int capacityA, int capacityB) {
        int n = plants.length, res = 0;
        int left = 0, right = n - 1, restA = capacityA, restB = capacityB;

        while (left <= right) {
            if (left == right) {
                if (restA < plants[left] && restB < plants[left]) res++;
                break;
            } else {
                if (restA >= plants[left]) restA -= plants[left++];
                else {
                    restA = capacityA - plants[left++];
                    res++;
                }
                if (restB >= plants[right]) restB -= plants[right--];
                else {
                    restB = capacityB - plants[right--];
                    res++;
                }
            }
        }
        return res;
    }



    // 2960. 统计已测试设备
    public int countTestedDevices(int[] batteryPercentages) {
        int res = 0;
        for (int x : batteryPercentages) {
            if (x - res > 0) res++;
        }
        return res;
    }



    // 2391. 收集垃圾的最少总时间
    public int garbageCollection(String[] garbage, int[] travel) {
        int res = 0;
        int M = 0, P = 0, G = 0;
        for (int i = 0; i < garbage.length; i++) {
            for (int j = 0; j < garbage[i].length(); j++) {
                res++;
                char ch = garbage[i].charAt(j);
                if (ch == 'M' && M != i) {
                    while (M != i) res += travel[M++];
                } else if (ch == 'P' && P != i) {
                    while (P != i) res += travel[P++];
                } else if (ch == 'G' && G != i){
                    while (G != i) res += travel[G++];
                }
            }
        }
        return res;
    }



    // 994. 腐烂的橘子
    private final int[] dx = new int[]{0,0,1,-1};
    private final int[] dy = new int[]{1,-1,0,0};
    public int orangesRotting(int[][] grid) {
        int n = grid.length, m = grid[0].length, sum = 0;
        Queue<int[]> q = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (grid[i][j] == 1) sum++;
                else if (grid[i][j] == 2) q.offer(new int[]{i, j});
            }
        }
        if (sum == 0) return 0;

        int time = 0;
        while (!q.isEmpty()) {
            time++;
            for (int sz = q.size(); sz-- > 0; ) {
                int[] arr = q.poll();
                int i = arr[0], j = arr[1];
                for (int k = 0; k < 4; k++) {
                    int x = i + dx[k], y = j + dy[k];
                    if (x >= 0 && x < n && y >= 0 && y < m && grid[x][y] == 1) {
                        grid[x][y] = 2;
                        q.offer(new int[]{x, y});
                        if (--sum == 0) return time;
                    }
                }
            }
        }
        return -1;
    }



    // 2244. 完成所有任务需要的最少轮数
    public int minimumRounds(int[] tasks) {
        Map<Integer, Integer> hash = new HashMap<>();
        // 统计每个难度的任务出现的次数
        for (int x : tasks) {
            hash.put(x, hash.getOrDefault(x, 0) + 1);
        }

        int res = 0;
        // 对每个任务依次进行枚举,尽量多的做3个任务
        for (Integer task : hash.keySet()) {
            int count = hash.get(task);
            int x = count / 3;
            while ((count - 3 * x) % 2 != 0) {
                x--;
            }
            if (x == -1) return -1;
            res += x + (count - 3 * x) / 2;
        }
        return res;
    }



    // 1953. 你可以工作的最大周数
    public long numberOfWeeks(int[] milestones) {
        // 统计每个工作出现的次数
        // 统计项目的阶段任务的最大数量
        long sum = 0, max = 0;
        for (int x : milestones) {
            sum += x;
            max = Math.max(max, x);
        }

        // 如果 max <= (sum + 1) / 2,则说明可以完成全部阶段任务
        if (max <= (sum + 1) / 2) return sum;
        return (sum - max) * 2 + 1;
    }



    // 1535. 找出数组游戏的赢家
    public int getWinner(int[] arr, int k) {
        int n = arr.length;
        int max = 0;
        for (int x : arr) {
            if (x > max) max = x;
        }

        if (k >= n - 1) return max;
        int left = 0, right = 1, count = k;
        while (count > 0) {
            if (arr[left] > arr[right]) {
                right = (right + 1) % n;
                if (--count == 0) return arr[left];
            } else {
                left = right;
                right = (right + 1) % n;
                count = k - 1;
            }
        }
        return arr[left];
    }



    // 2903. 找出满足差值条件的下标 I
    public int[] findIndices(int[] nums, int indexDifference, int valueDifference) {
        int n = nums.length;
        for (int i = 0; i < n - indexDifference; i++) {
            for (int j = i + indexDifference; j < n; j++) {
                if (Math.abs(nums[i] - nums[j]) >= valueDifference) {
                    return new int[]{i ,j};
                }
            }
        }
        return new int[]{-1, -1};
    }


    // 2225. 找出输掉零场或一场比赛的玩家
    public List<List<Integer>> findWinners(int[][] matches) {
        boolean[] exists = new boolean[100001];
        int[] fails = new int[100001];
        // 1. 统计是否打过比赛及失败次数
        for (int[] match : matches) {
            int winner = match[0], loser = match[1];
            exists[winner] = exists[loser] = true;
            fails[loser]++;
        }

        // 2. 返回结果
        List<List<Integer>> ret = new ArrayList<>();
        ret.add(new ArrayList<>());
        ret.add(new ArrayList<>());
        for (int i = 1; i <= 100000; i++) {
            if (exists[i]) {
                if (fails[i] == 0) ret.get(0).add(i);
                if (fails[i] == 1) ret.get(1).add(i);
            }
        }

        // 3. 将返回结果排序
        ret.get(0).sort((a, b) -> a - b);
        ret.get(1).sort((a, b) -> a - b);
        return ret;
    }




    // 2028. 找出缺失的观测数据
    public int[] missingRolls(int[] rolls, int mean, int n) {
        int m = rolls.length, sum = 0;
        for (int x : rolls) {
            sum += x;
        }
        sum = (n + m) * mean - sum;
        if (sum < n || sum > n * 6) return new int[0];

        int[] res = new int[n];
        for (int i = n; i > 0; i--) {
            res[i - 1] = sum / i;
            sum -= sum / i;
        }
        return res;
    }


    // 2951. 找出峰值
    public List<Integer> findPeaks(int[] mountain) {
        List<Integer> res = new ArrayList<>();
        int prev = mountain[0];
        for (int i = 1; i < mountain.length - 1; i++) {
            if (mountain[i] > prev && mountain[i] > mountain[i + 1]) {
                res.add(i);
            }
            prev = mountain[i];
        }
        return res;
    }



    // 2965. 找出缺失和重复的数字
    public int[] findMissingAndRepeatedValues(int[][] grid) {
        int n = grid.length;
        boolean[] exists = new boolean[n * n + 1];

        int[] res = new int[2];
        for (int[] arr : grid) {
            for (int x : arr) {
                if (exists[x]) res[0] = x;
                exists[x] = true;
            }
        }

        for (int i = 1; i <= n * n; i++) {
            if (!exists[i]) {
                res[1] = i;
                break;
            }
        }
        return res;
    }



    // 1103. 分糖果 II
    public int[] distributeCandies(int candies, int num_people) {
        int[] res = new int[num_people];
        for (int i = 0, k = 1; candies > 0; i = (i + 1) % num_people) {
            if (candies >= k) {
                res[i] += k;
                candies -= k;
            } else {
                res[i] += candies;
                candies = 0;
            }
            k++;
        }
        return res;
    }



    // 3038. 相同分数的最大操作数目 I
//    public int maxOperations(int[] nums) {
//        int res = 1, sum = nums[0] + nums[1];
//        for (int i = 2, n = nums.length; i + 1 < n; i += 2) {
//            if (nums[i] + nums[i + 1] == sum) res++;
//            else break;
//        }
//        return res;
//    }



    // 3040. 相同分数的最大操作数目 II
    private int n;
    private int res;
    private int[][] memo;
    private int[] nums;
    public int maxOperations(int[] nums) {
        this.nums = nums;
        n = nums.length;
        memo = new int[n][n];
        helper(2, n - 1, 0, nums[0] + nums[1]);
        helper(1, n - 2, 0, nums[0] + nums[n - 1]);
        helper(0, n - 3, 0, nums[n - 1] + nums[n - 2]);
        return res;
    }
    private void helper(int left, int right, int count, int sum) {
        for (int[] arr : memo) {
            // 表示未计算过
            Arrays.fill(arr, -1);
        }
        dfs(left, right, count, sum);
    }
    private int dfs(int left, int right, int count, int sum) {
        count++;
        if (left >= right) {
            res = Math.max(res, count);
            return count;
        }
        if (memo[left][right] != -1) return memo[left][right];

        int ret = 0;
        if (nums[left] + nums[left + 1] == sum) {
            ret = Math.max(ret, dfs(left + 2, right, count, nums[left] + nums[left + 1]));
        }
        if (nums[left] + nums[right] == sum) {
            ret = Math.max(ret, dfs(left + 1, right - 1, count, nums[left] + nums[right]));
        }
        if (nums[right - 1] + nums[right] == sum) {
            ret = Math.max(ret, dfs(left, right - 2, count, nums[right - 1] + nums[right]));
        }
        res = Math.max(res, count);
        memo[left][right] = ret;
        return memo[left][right];
    }



    // 2806. 取整购买后的账户余额
    public int accountBalanceAfterPurchase(int purchaseAmount) {
        int i = 0;
        while (Math.abs(i * 10 - purchaseAmount) > 10) i++;

        int a = Math.abs(i * 10 - purchaseAmount);
        int b = Math.abs((i + 1) * 10 - purchaseAmount);
        if (a >= b) {
            return 100 - (i + 1) * 10;
        }
        return 100 - i * 10;
    }




    // 881. 救生艇
    public int numRescueBoats(int[] people, int limit) {
        Arrays.sort(people);
        int n = people.length;
        int left = 0, right = n - 1;

        int ret = 0;
        while (left < right) {
            if (people[left] + people[right] <= limit) {
                left++;
            }
            right--;
            ret++;
        }
        if (left == right) ret++;
        return ret;
    }





    // 2786. 访问数组中的位置使分数最大
    public long maxScore(int[] nums, int x) {
        int n = nums.length;

        // dp[i][j]: 从右向左
        long[][] dp = new long[n + 1][2];
        for (int i = n - 1; i >= 0; i--) {
            int mod = nums[i] % 2;
            dp[i][mod ^ 1] = dp[i + 1][mod ^ 1];
            dp[i][mod] = Math.max(dp[i + 1][mod], dp[i + 1][mod ^ 1] - x) + nums[i];
        }
        return dp[0][nums[0] % 2];
    }
    // 递归 -> 记忆化搜索
//    private int[] nums;
//    private long[][] memo;
//    private int n;
//    public long maxScore(int[] nums, int x) {
//        this.nums = nums;
//        this.n = nums.length;
//        memo = new long[n][2];
//        // 表示该状态还没被搜索过
//        for (long[] arr : memo) {
//            Arrays.fill(arr, -1);
//        }
//        return dfs(0, nums[0] % 2, x);
//    }
//    // 在下标 pos ~ n-1 的区间中寻找一个子序列,其中第一个数的 余数==mod,所能获得的最大得分和
//    private long dfs(int pos, int mod, int x) {
//        if (pos == nums.length) {
//            return 0;
//        }
//        if (memo[pos][mod] != -1) return memo[pos][mod];
//
//        if (nums[pos] % 2 != mod)  {
//            return memo[pos][mod] = dfs(pos + 1, mod, x);
//        }
//        long res1 = dfs(pos + 1, mod, x) + nums[pos];
//        long res2 = dfs(pos + 1, (mod + 1) % 2, x) + nums[pos] - x;
//
//        memo[pos][mod] = Math.max(res1, res2);
//        return memo[pos][mod];
//    }


    // 2779. 数组的最大美丽值
    public int maximumBeauty(int[] nums, int k) {
        Arrays.sort(nums);

        // 排序 + 滑动窗口
        int res = 0;
        int left = 0, right = 0;
        for (int n = nums.length; right < n; right++) {
            while (nums[right] - nums[left] > 2 * k) {
                left++;
            }
            res = Math.max(res, right - left + 1);
        }
        return res;
    }
    //public int maximumBeauty(int[] nums, int k) {
    //        Arrays.sort(nums);
    //
    //        // 排序 + 枚举 + 2分
    //        int res = 0;
    //        for (int i = nums[0], n = nums.length; i <= nums[n - 1]; i++) {
    //            int[] indexs = getIndexs(nums, i, k);
    //            res = Math.max(res, indexs[1] - indexs[0] + 1);
    //        }
    //        return res;
    //    }
    //    // 获取非递减数组中,以 num 为基准,值小于num-k的最右边界和值大于num+k的最左边界
    //    private int[] getIndexs(int[] nums, int num, int k) {
    //        int[] res = new int[2];
    //        int n = nums.length;
    //        int left = 0, right = n - 1, mid = 0;
    //        while (left < right) {
    //            mid = left + (right - left) / 2;
    //            if (nums[mid] < num - k) left = mid + 1;
    //            else right = mid;
    //        }
    //        res[0] = left;
    //
    //        for (left = 0, right = n - 1; left < right; ) {
    //            mid = left + (right - left + 1) / 2;
    //            if (nums[mid] > num + k) right = mid - 1;
    //            else left = mid;
    //        }
    //        res[1] = left;
    //        return res;
    //    }

}
